package com.lw.leetcode.back.b;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 1466. 重新规划路线
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/9 15:27
 */
public class MinReorder {


    public static void main(String[] args) {
        MinReorder test = new MinReorder();

        // 3
        int n = 6;
        int[][] arr = {{0, 1}, {1, 3}, {2, 3}, {4, 0}, {4, 5}};
        int i = test.minReorder(n, arr);
        System.out.println(i);

    }


    private Map<Integer, List<Integer>> map = new HashMap<>();
    private int count = 0;

    public int minReorder(int n, int[][] connections) {

        Map<Integer, List<Integer>> map = new HashMap<>(n);
        for (int[] connection : connections) {
            List<Integer> list = map.computeIfAbsent(connection[0], v -> new ArrayList<>());
            list.add(connection[1]);
            list = map.computeIfAbsent(connection[1], v -> new ArrayList<>(2));
            list.add(~connection[0] + 1);
        }
        this.map = map;
        find(Integer.MIN_VALUE, 0);
        return n - 1 - count;
    }

    private void find(int last, int key) {
        List<Integer> list = map.get(key);
        for (int value : list) {
            if (value == last || value + last == 0) {
                continue;
            }
            if (value < 0) {
                find(key, ~value + 1);
                count++;
            } else {
                find(key, value);
            }
        }
    }

}
